home *** CD-ROM | disk | FTP | other *** search
/ FishMarket 1.0 / FishMarket v1.0.iso / fishies / 426-450 / disk_438 / toollib / source / qsort.s < prev    next >
Text File  |  1992-05-06  |  4KB  |  104 lines
  1.             opt     l+,o+,ow-
  2. *
  3. *   qsort.s version 7.6 - © Copyright 1990 Jaba Development
  4. *
  5. *   Author    : Jan van den Baard
  6. *   Assembler : Devpac vesion 2.14
  7. *
  8.             incdir  'sys:devpac_inc/'
  9.             include 'mymacros.i'
  10.  
  11.             xdef    SwapMem
  12.             xdef    QuickSort
  13.  
  14. *
  15. * QuickSort(base,num,size,compar)
  16. *            a0   d0  d1   a1
  17. *
  18. QuickSort:  move.l  a1,-(sp)
  19.             movem.l d0-d1,-(sp)
  20.             move.l  a0,-(sp)
  21.             bsr.s   QSort
  22.             lea.l   16(sp),sp
  23.             rts
  24. *
  25. * sort an array of elements.
  26. * this routine is recursive it needs a lot of stack when sorting
  27. * a large number of elements!
  28. * the elements in the array may NOT be bigger than 64 KByte!
  29. *
  30. QSort:      movem.l d2-d5/a2-a3,-(sp)
  31.             move.l  28(sp),a2               ; array base
  32.             move.l  32(sp),d2               ; number of elements
  33.             move.l  36(sp),d3               ; size of a element
  34.             move.l  40(sp),a3               ; comparrison routine
  35.             tst.l   d2                      ; sort if there are elements
  36.             bne.s   SortIt
  37. EndQS:      movem.l (sp)+,d2-d5/a2-a3
  38.             rts
  39. SortIt:     cldat   d4                      ; offset = 0
  40.             moveq   #1,d5                   ; n = 1
  41.             bra.s   ChkEnd                  ; check if all are done
  42. CmpLoop:    move.l  a2,-(sp)                ; base[0] = x
  43.             move.l  d3,d0
  44.             mulu    d5,d0
  45.             add.l   a2,d0
  46.             move.l  d0,-(sp)
  47.             jsr     (a3)                    ; cmp(base+(n*size),x);
  48.             addq.w  #8,sp
  49.             tst.l   d0
  50.             bge.s   NoSwap                  ; if result >= 0 then dont swap
  51.             inc.l   d4                      ; offset++
  52.             move.l  d3,d1                   ; size
  53.             move.l  a2,a0
  54.             move.l  d3,d0
  55.             mulu    d5,d0
  56.             add.l   d0,a0                   ; base + (n*size)
  57.             move.l  a2,a1
  58.             move.l  d3,d0
  59.             mulu    d4,d0
  60.             add.l   d0,a1                   ; base + (offset*size)
  61.             bsr.s   SwapMem                 ; SwapMem()
  62. NoSwap:     inc.l   d5                      ; n++
  63. ChkEnd:     cmp.l   d2,d5                   ; n < num ?
  64.             bcs.s   CmpLoop                 ; if so.. loop
  65.             move.l  d3,d1                   ; size
  66.             move.l  a2,a0                   ; base
  67.             move.l  a2,a1
  68.             move.l  d3,d0
  69.             mulu    d4,d0
  70.             add.l   d0,a1                   ; base + (offset*size)
  71.             bsr.s   SwapMem                 ; SwapMem()
  72.             move.l  a3,-(sp)                ; cmp()
  73.             move.l  d3,-(sp)                ; size
  74.             move.l  d4,-(sp)                ; offset
  75.             move.l  a2,-(sp)                ; base
  76.             bsr.s   QSort                   ; QSort()
  77.             addq.w  #8,sp
  78.             move.l  d2,d0
  79.             sub.l   d4,d0
  80.             dec.l   d0
  81.             move.l  d0,-(sp)                ; num - offset - 1
  82.             move.l  d3,d0
  83.             mulu    d4,d0
  84.             add.l   d3,d0
  85.             add.l   a2,d0
  86.             move.l  d0,-(sp)                ; base + (offset*size) + size
  87.             bsr.s   QSort                   ; QSort
  88.             lea.l   16(sp),sp
  89.             bra.s   EndQS
  90.  
  91. *
  92. * SwapMem(mema,memb,size)
  93. *          a0   a1   d1
  94. * this routine does NOT swap memory chunks bigger than 64 Kbyte! (should be
  95. * enough)
  96. *
  97. SwapMem:    bra.s   ChkDone
  98. Swap:       move.b  (a0),d0                 ; byte = *area1
  99.             move.b  (a1),(a0)+              ; *area1++ = *area2
  100.             move.b  d0,(a1)+                ; *area2++ = byte
  101. ChkDone:    dbra    d1,Swap                 ; loop until 'size' bytes done
  102.             rts
  103.  
  104.